class Solution {
public:
    /*
    // 先序
    bool IsBalanced_Solution(TreeNode* p) {
        if(!p) return true;
        if(abs(GetHeight(p->left)-GetHeight(p->right)) > 1) return false;
        return IsBalanced_Solution(p->left) && IsBalanced_Solution(p->right);
    }
    int GetHeight(TreeNode* cur) {
        if(!cur) return 0;
        return max(GetHeight(cur->left),GetHeight(cur->right))+1;
    }
    */
    // 后序
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return dfs(pRoot)!=-1;
    }
    // 返回该节点的高度，如果以该节点为根节点的子树不满足AVL条件就返回-1
    int dfs(TreeNode* cur) {
        if(!cur) return 0;
        int left = dfs(cur->left);
        if(left == -1) return -1;
        int right = dfs(cur->right);
        if(right == -1) return -1;
        int tmp = abs(left-right);
        if(tmp > 1) return -1;
        return max(left, right) + 1;
    }
};